package compress;

import java.util.PriorityQueue;

/**
 * 哈夫曼算法一般用于压缩，是一种无损压缩算法
 *
 * 算法思想：出现次数最多的字符用最短的编码表示，出现次数少的字符用长的编码表示，这样综合下来编码总长度比以前小
 *
 * 算法实现：生成一棵完全二叉树，叶子节点表示字符，非叶子节点的值等于两子节点值的和，根据根节点到叶子节点的路径来表示字符的编码，左边用0表示，右边用1表示
 */
public class Huffman {

    // 内部节点类
    public static class Node implements Comparable<Node> {
        char ch;
        int freq;
        Node left, right;

        public Node(char ch, int freq, Node left, Node right) {
            this.ch = ch;
            this.freq = freq;
            this.left = left;
            this.right = right;
        }

        public boolean isLeaf() {
            return left == null && right == null;
        }

        public int compareTo(Node other) {
            return this.freq - other.freq;
        }
    }

    public static Node buildHuffmanTree(int[] freq) {
        //先构建一个小顶堆
        PriorityQueue<Node> pq = new PriorityQueue<>();
        for (char i = 0; i < freq.length; i++) {
            if (freq[i] > 0) {
                pq.offer(new Node(i, freq[i], null, null));
            }
        }

        //取出最小的两个节点，合并为一个节点，并放入堆中重复此步骤，直到堆中只有一个节点(也就是根节点)
        while (pq.size() > 1) {
            Node left = pq.poll();
            Node right = pq.poll();
            pq.offer(new Node('\0', left.freq + right.freq, left, right));
        }
        return pq.poll();
    }

    /**
     * 打印每个字符的编码
     * @param root
     * @param code
     */
    public static void printCodes(Node root, String code) {
        if (root.isLeaf()) {
            System.out.println(root.ch + " : " + code);
        } else {
            printCodes(root.left, code + "0");
            printCodes(root.right, code + "1");
        }
    }

    public static void main(String[] args) {
        String str = "Hello World!";
        int[] freq = new int[256];
        for (char c : str.toCharArray()) {
            //遇到相同的字符+1
            freq[c]++;
        }
        Node root = buildHuffmanTree(freq);
        printCodes(root, "");
    }
}
